\documentclass[a4paper,10pt]{article}

%linguagem
\usepackage[brazil]{babel}
%encodificação
\usepackage[utf8]{inputenc}
%biblioteca de matemática
\usepackage{amssymb,amsmath}
%pacote para codigo fonte
\usepackage{listings}
%figuras
\usepackage{graphicx}
%cores
\usepackage{color}
%paragrafo no inicio da secao
\usepackage{indentfirst}
%url
\usepackage{framed, url}
\usepackage{fancyvrb}

%define a cor "claro"
\definecolor{claro}{gray}{0.96}

%configurações do fancy verbatim
\fvset{frame=single, xleftmargin=-80pt, xrightmargin=-80pt}
%configurações do listings
\lstset{frame=trBL, numbers=left, xleftmargin=0pt, xrightmargin=0pt,
breaklines=true, backgroundcolor=\color{claro}}

\begin{document}

\input{./titulo.tex}
\tableofcontents
\pagebreak

\section{Introdução}
O compilador é o programa responsável por transformar um código-fonte de uma
linguagem de programação em outra linguagem, geralmente um código binário, ou
executável. O processo de compilação é feito através de várias etapas, como
mostrado na figura \ref{fig:fases}. 

\begin{figure}[h] 
\centering
\includegraphics[scale=0.6]{imagens/fases.png} 
\label{fig:fases} 
\caption{Fases do processo de compilação} 
\end{figure}

Depois da geração de código pelo compilador, um interpretador é usado para
executar as instruções contidas neste código e finalmente realizar as tarefas
descritas no código-fonte feito pelo programador.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/interpretador.png}
\label{fig:interpretador}
\caption{Interpretador}
\end{figure}


O objetivo deste trabalho é implementar a segunda fase do processo de
compilação, a análise sintática. Ela é responsável pelas seguintes tarefas:
\begin{itemize}
\item Receber uma cadeia de tokens do analisador léxico.
\item Verificar se a cadeia de tokens pertence à linguagem gerada pela
gramática.
\item Emitir mensagens de erro e se recuperar desses erros.
\item Construir uma árvore de derivação e passá-la ao restante do {\it
front-end} do compilador.
\end{itemize}

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/parser.png}
\label{fig:parser}
\caption{Posição do analisador sintático (parser) no modelo de compilador.}
\end{figure}
 
\section{Desenvolvimento}

Para implementar a análise léxica, utilizamos as ferramentais {\it lex} e {\it
yacc}. 
\subsection{Lex}

O programa Lex é um gerador de analisadores léxicos, através da definição de
expressões regulares para descrever padrões para os tokens. A notação de entrada
para a ferramenta {\it Lex} é chamada de {\it linguagem Lex}, e a ferramenta em
si é o {\it compilador Lex}. Internamente, o compilador Lex transforma os
padrões de entrada em m diagrama de transição e gera código em um arquivo
chamado lex.yy.c, que simula esse diagrama de transição.

\begin{figure}[h] 
\centering
\includegraphics[scale=0.6]{imagens/lex.png} 
\label{fig:lex} 
\caption{Utilização do Lex} 
\end{figure}

Um programa Lex possui o seguinte formato:

\begin{Verbatim}
                declarações
                %%  
                regras de tradução
                %%
                funções auxiliares
\end{Verbatim}

A seção de declarações inclui declarações de variáveis, constantes manifestas e
definições regulares. Cada uma das regras de tradução possui o formato:

\begin{center}
Padrão \{ Ação \}
\end{center}

\subsection{Yacc}

Yacc é o gerador de analisador sintático utilizado neste trabalho. Um tradutor
pode ser construído usando o Yacc. Inicialmente, prepara-se um arquivo, digamos,
translate.y, contendo uma especificação Yacc dor tradutor. O comando do sistema
UNIX

\medskip
\colorbox{claro}{\$ yacc -d translate.y}
\medskip

transforma o arquivo translate.y em um programa C chamado y.tab.c, usando o
método LALR. O programa y.tab.c é uma representação de um analisador LALR
escrito em C, junto com outras rotinas C que o usuário pode ter preparado.
Compilando y.tab.c junto com a biblioteca ly que contém o programa de análise LR
usando o comando

\medskip
\colorbox{claro}{\$ cc y.tab.c -ly}
\medskip

obtemos o programa objeto desejado a.out, que realiza a tradução especificada
pelo programa Yacc original. Se outros procedimentos forem necessários, eles
podem ser compilados ou carregados com y.tab.c, assim como qualquer outro
programa em C.

\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{imagens/yacc.png}
\label{fig:yacc}
\caption{Utilização do Yacc}
\end{figure}


Um programa fonte Yacc possui três partes:

\begin{Verbatim}
                declarações
                %%   
                regras de tradução
                %%
                rotinas de suporte em C	
\end{Verbatim}


\pagebreak
\section{Gramática}

A gramática utilizada para realizar a análise sintática foi:

\VerbatimInput{../gramatica}


\section{Instruções para utilização}

Um arquivo de entrada, chamado lexemas.l, foi escrito na linguagem Lex e
descreve o analisador léxico a ser gerado. Através do comando:

\medskip
\colorbox{claro}{\$ lex lexemas.l} 
\medskip

o compilador Lex transforma lexemas.l em um programa C, e o armazena em um
arquivo que sempre se chama lex.yy.c.

Outro arquivo, chamado gramatica.y, foi escrito na linguagem Yacc e descreve a
gramática da linguagem. Usando o comando:

\medskip
\colorbox{claro}{\$ yacc -d gramatica.y}
\medskip

o Yacc transforma gramatica.y em um programa C, que é armazenado no arquivo
chamdo y.tab.c.

 Esses dois arquivos são compilados pelo gcc
pelo comando:

\medskip
\colorbox{claro}{\$ gcc -o parser lex.yy.c y.tab.c}
\medskip
 
que gera o executável, que é o analisador sintático propriamente dito.

Para executar o programa utilizando como entrada o arquivo in.txt, por exemplo, usa-se o
comando:

\medskip
\colorbox{claro}{\$ ./parser $<$ in.txt}
\medskip

\section{Testes}

Quase todos os testes apresentam erros de sintaxe.

\subsection{Teste A}

Erro: O tipo {\it real} não é aceito pela linguagem SL. 

Entrada:
\VerbatimInput{../testes/teste1.in}

Saída:

\VerbatimInput{../testes/teste1.out}

\subsection{Teste B}

Erro: A declaração {\it b:boolean} não é aceita.

Entrada:
\VerbatimInput{../testes/teste2.in}

Saída:

\VerbatimInput{../testes/teste2.out}

\subsection{Teste C}

Erro: O formato de declaração de arrays não está correto.

Entrada:
\VerbatimInput{../testes/teste3.in}

Saída:

\VerbatimInput{../testes/teste3.out}

\subsection{Teste D}

Não há erros no teste D.

Entrada:
\VerbatimInput{../testes/teste4.in}

Saída:

\VerbatimInput{../testes/teste4.out}

\subsection{Teste E}

Erro: A declaração {\it number : integer} é inválida.

Entrada:
\VerbatimInput{../testes/teste5.in}

Saída:

\VerbatimInput{../testes/teste5.out}

\subsection{Teste F}

Erro: A gramática SL não permite a construção {\it procedure p(procedure f)}.

Entrada:
\VerbatimInput{../testes/teste6.in}

Saída:

\VerbatimInput{../testes/teste6.out}

\subsection{Teste G}
Erro: A palavra {\it labe} não existe na linguagem SL.

Entrada:

\VerbatimInput{../testes/teste7.in}

Saída:

\VerbatimInput{../testes/teste7.out}

\clearpage
\section{Conclusão}
		
O desenvolvimento deste trabalho possibilitou o aprendizado acerca do
funcionamento de um analisador sintático. Pudemos aprender como funcionam as
ferramentas Lex e Yacc
e através delas fomos capazes de gerar o analisador sintático apropriado para a
linguagem SL. O desenvolvimento desse trabalho foi um passo muito importante para que o próximo trabalho seja
concluído, e que no final do curso um compilador seja implementado na íntegra.

\section{Código-fonte}

\subsection{lexemas.l}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../lexemas.l}

\subsection{gramatica.y}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../gramatica.y}


\clearpage
\begin{thebibliography}{99}
\bibitem{wiki} \url{en.wikipedia.org/wiki/Lex_(software)}
\bibitem{tut1} \url{http://dinosaur.compilertools.net/lex/index.html}
\bibitem{tut2} \url{http://ds9a.nl/lex-yacc/cvs/output/lexyacc.html}
\bibitem{tut3} \url{http://osr507doc.sco.com/en/tools/Lex_yacc.html}
\bibitem{livro} Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, \emph{Compilers - Principles Techniques and Tools}, 2006
\end{thebibliography}

\end{document}
